This invention relates to integrated circuits (“ICs”). More particularly, this invention relates to multiplexer circuitry in ICs.
Multiplexers are well-known circuits that accept N selector inputs and 2N data inputs, and generate a single data output. Each binary combination of the N selector inputs will select a corresponding data input and transmit its value to the data output. For simplicity of illustration, the discussion herein will focus on multiplexers with a single selector input, two data inputs, and one data output. However, it will be understood that the concepts discussed herein could be generalized to accommodate N selector inputs and 2N data inputs.
Multiplexers are used extensively in ICs, and are especially common in the datapaths of programmable logic devices (“PLDs”). Such datapaths often include “multiplexer cones,” which are composed of a plurality of multiplexers feeding into each other. That is, the output of each multiplexer is coupled to a data input of another multiplexer, with the exception of the final multiplexer in the cone, which typically drives a register or other output circuitry. Because datapaths often consist of multiple bits, PLDs typically include many “multiplexer cone buses,” which are collections of multiplexer cones that are isomorphic to each other and share the same selector inputs. In addition, wherever a pair of data inputs are electrically equivalent in one multiplexer cone, they are also equivalent in the other cones of the same bus, a property that will become significant later herein.
Because of the prevalence of multiplexer circuitry in ICs, and in PLDs in particular, it is highly desirable to find algorithms that can reduce the cost (e.g., area) of multiplexer circuitry. Such reduction can be achieved, for example, during synthesis, where software code that is written in a hardware description language (“HDL”) is converted into a circuit configuration that can be implemented on an IC. Modern synthesis algorithms typically optimize multibit datapaths one bit at a time. As a result, some optimizations that can yield savings if applied across an entire multiplexer cone bus, but not if applied to individual multiplexer cones, are not used.
In view of the foregoing, it would be desirable to provide methods and apparatus that can reduce the cost of multiplexer circuitry. In particular, it would be desirable to provide methods and apparatus that can reduce the cost of multiplexer cone buses.